686. Следующий

Реализуйте структуру данных, которая поддерживает множество S целых чисел, с которым разрешается производить следующие операции:

· add(i) – добавить в множество S число i (если оно там уже есть, то множество не меняется);

· next(i) – вывести минимальный элемент множества, не меньший i. Если искомый элемент в структуре отсутствует, необходимо вывести –1.

Вход. Исходное множество S пусто. Первая строка содержит количество операций n (1 ≤ n ≤ 300 000). Следующие n строк содержат операции. Каждая операция имеет вид либо "+ i", либо "? i". Операция "? i" задает запрос next(i).

Если операция "+ i" идет в начале или после другой операции "+", то она задает операцию add(i). Если же она идет после запроса "?" и результат этого запроса был y, то выполняется операция add((i + y) mod 10⁹).

Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 10⁹.

Выход. Для каждого запроса выведите одно число – ответ на запрос.

Пример входа	Пример выхода
6 + 1 + 3 + 3 ? 2 + 1 ? 4	3 4

РЕШЕНИЕ

структуры данных – декартово дерево, явный ключ

Анализ алгоритма

Для решения задачи используем декартово дерево с явным ключом. Достаточно реализовать операции вставки элемента в дерево и нахождения минимального элемента множества, не меньшего i. Для реализации последней операции достаточно разрезать дерево по ключу i (получив левое L и правое R дерево), после чего вернуть минимальный ключ дерева R.

Пример

Рассмотрим приведенный в примере тест.

Вход	Операция	Содержимое множества S	Выводимое значение
+ 1	add(1)	{1}
+ 3	add(3)	{1, 3}
+ 3	add(3)	{1, 3}
? 2	next(2)	{1, 3}	3
+ 1	add(1 + 3) = add(4)	{1, 3, 4}
? 4	next(4)	{1, 3, 4}	4

Реализация алгоритма

Объявим структуру item вершины декартового дерева. Объявим указатель pitem на нее.

struct item

{

int Key, Priority;

item *l, *r;

item() { }

item (int Key, int Priority) :

Key(Key), Priority(Priority), l(NULL), r(NULL) { }

};

typedef item* pitem;

Функцию split разрезания дерева t по ключу Key реализуем так, чтобы элемент дерева, равный ключу Key, отходил в правое поддерево r.

void split (pitem t, int Key, pitem &l, pitem &r)

{

if (!t)

l = r = NULL;

else if (Key <= t->Key)

split (t->l, Key, l, t->l), r = t;

else

split (t->r, Key, t->r, r), l = t;

}

Функция merge сливает два декартовых дерева l и r в t.

void merge (pitem l, pitem r, pitem &t)

{

if (!l || !r)

t = l ? l : r;

else if (l->Priority > r->Priority)

merge (l->r, r, l->r), t = l;

else

merge (l, r->l, r->l), t = r;

}

Функция GetMin возвращает минимальный ключ в дереве t.

int GetMin(pitem t)

{

if (t == NULL) return -1;

if (t->l == NULL) return t->Key;

return GetMin(t->l);

}

Реализация операции add. Если элемент с ключом i уже присутствует в дереве, то после разреза он будет минимальным в R. В таком случае (когда GetMin(R) равно i) ничего добавлять не надо, но следует склеить дерево Tree обратно. Иначе добавляем новый элемент с ключом i методом вклейки. Приоритет каждого нового элемента выбираем произвольно при помощи функции rand(), чтобы строящееся декартово дерево Tree было максимально сбалансировано.

void add(int i)

{

split(Tree,i,L,R);

if(GetMin(R) != i)

{

merge(L,new item(i,rand()),Tree);

merge(Tree,R,Tree);

}

else merge(L,R,Tree);

}

Реализация операции next. Разрезаем дерево Tree по ключу i. Выводим минимальный элемент правого полученного дерева R. Собираем дерево Tree обратно.

void next(int i)

{

split(Tree,i,L,R);

y = GetMin(R);

printf("%d\n",y);

merge(L,R,Tree);

}

Основная часть программы. Читаем входные данные и обрабатываем запросы. Переменную y устанавливаем в MINF = -2000000000, если предыдущим не был запрос “?”.

#define MINF -2000000000

int y = MINF;

scanf("%d\n",&n);

while(n--)

{

scanf("%c %d\n",&c,&i);

if (c == '+')

{

if (y > MINF) i = (i + y) % 1000000000, y = MINF;

add(i);

}

else next(i);

}